A linked list is a data structure that can be used to implement other data structures. A linked list typically includes a sequence of nodes, with each node including a value and one or two references or links that point to adjacent node(s). In a singly-linked list, the nodes each include a single link that points to the next node. In a doubly-linked list, the nodes each include a first link that points to the previous node and a second link that points to the next node.
Out of all of the concurrent data structures, a linked list is difficult to make thread-safe due to the typically unrestricted arbitrary access to the list's nodes. In contrast to queues and stacks that typically provide access strictly to end nodes, linked lists typically allow direct access to any node, complicating semantics and a scalable implementation.